/*
 * Поиск строк
 *
 * Aho-Corasick
 */

#include <stdio.h>
#include <stdbool.h>
#include <stdint.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>
#include <limits.h>
#include <assert.h>

/* #define DEBUG */
/* #define MEMDEBUG */

#ifdef DEBUG
# define debug_fprintf(x)	fprintf x
#else
# define debug_fprintf(x)	((void) 0)
#endif
#define S_assert(st) ((st)?((void)0):(void)fprintf(stderr,"Assertion (soft) \"%s\" in %s:%s():%d: failed.\n",#st,__FILE__,__func__,__LINE__))
#define SWAP_INT(a, b)	(((a) ^ (b)) && ((b) ^= (a) ^= (b), (a) ^= (b)))
#define MIN(a, b)	((a) < (b) ? (a) : (b))

/* autoarray */
struct vector {
	char *data;
	size_t _elem_size;

	int n;
	int _max;
};

/* queue */
struct queue {
	char *data;
	size_t _data_size;

	int head;
	int n;
	int _max;
};

struct ac_node {
	struct ac_node *prefix;
	struct ac_node *out;

	struct ac_node *next['z' - 'a' + 1];

	bool final_pattern, root;
	int pattern_id;
	int pattern_len; /* same as distance from root? */
};

struct twotuple {
	int a, b;
};

/* {{{ memory allocation wrappers */
extern char *
s_calloc(size_t n, size_t size)
{
	void *ptr;
#ifdef MEMDEBUG
	fprintf(stderr, "%s(): calloc %lu times %lu bytes (tot %.4f MiB)\n",
			__func__, n, size, ((float) n * size) / (1024.0f * 1024.0f));
#endif /* MEMDEBUG */
	ptr = calloc(n, size);
	if (ptr == NULL) {
		fprintf(stderr, "%s(): out of memory, failed to allocate %lu bytes\n",
				__func__, n * size);
		abort();
	}
	return ptr;
}

extern char *
s_malloc(size_t size)
{
	void *ptr;
#ifdef MEMDEBUG
	fprintf(stderr, "%s(): malloc %lu bytes (%.4f MiB)\n",
			__func__, size, (float) size / (1024.0f * 1024.0f));
#endif /* MEMDEBUG */
	ptr = malloc(size);
	if (ptr == NULL) {
		fprintf(stderr, "%s(): out of memory, failed to allocate %lu bytes\n",
				__func__, size);
		abort();
	}
	return ptr;
}

extern char *
s_realloc(char *oldptr, size_t newsize)
{
	void *newptr;
#ifdef MEMDEBUG
	fprintf(stderr, "%s(): realloc oldptr %p for new size of %lu (%.4f MiB)\n",
			__func__, oldptr, newsize, (float) newsize / (1024.0f * 1024.0f));
#endif
	newptr = realloc(oldptr, newsize);
	if (newptr == NULL) {
		fprintf(stderr, "%s(): out of memory, "
				"failed to realloc %p for new size of %lu bytes\n",
				__func__, oldptr, newsize);
		abort();
	}
#ifdef MEMDEBUG
	fprintf(stderr, "%s(): newptr %p\n", __func__, newptr);
#endif /* MEMDEBUG */
	return newptr;
}
/* }}} */

/* {{{ autoarray */
extern struct vector *
vector__new(size_t elem_size, int p)
{
	struct vector *v = NULL;

	if (p < 0)
		p = 0;

	v = (struct vector *) s_malloc(sizeof *v);
	v->_max = 1 << p;
	v->_elem_size = elem_size;
	v->n = 0;
	v->data = (char *) s_calloc((size_t) v->_max, v->_elem_size);

	return v;
}

extern int
vector__append(struct vector *v, const void *app)
{
	int ret = 0;

	if (v == NULL) {
		fprintf(stderr, "%s(): received NULL ptr, not doing anything (-1)\n",
				__func__);
		return -1;
	}

	if (v->_max == 0) {
		/* weird input, fix it */
		ret |= 2;
		debug_fprintf((stderr, "%s(): v->_max is 0, which means that your "
					"autoarray (v=%p) is messed up. trying to fix this.\n",
					__func__, (void*) v));
		if (v->_elem_size == 0) {
			ret |= 4;
			fprintf(stderr, "%s(): can't fix this mess, bailing out (%d)\n",
					__func__, ret);
			return ret;
		} else {
			v->_max = 1;
			v->n = 0;
			v->data = (char *) s_calloc((size_t) v->_max, v->_elem_size);
		}
	}

	if (v->n + 1 >= v->_max) {
		v->data = (char *) s_realloc(v->data, v->_elem_size * (v->_max *= 2));
	}
	memcpy(v->data + (v->n++) * v->_elem_size, app, v->_elem_size);

	return ret;
}

extern char *
vector__get_by_idx(struct vector *v, const int idx)
{
	if (v == NULL) {
		fprintf(stderr, "%s(): received NULL ptr, not doing anything (NULL)\n",
				__func__);
		return NULL;
	}

	if (v->_elem_size == 0) {
		fprintf(stderr, "%s(): whoah, looks like your vector is messed up big time (NULL)\n",
				__func__);
		return NULL;
	}

	if (idx < 0 || idx >= v->n) {
		fprintf(stderr, "%s(): index out of range %d (v->n=%d)\n",
				__func__, idx, v->n);
		return NULL;
	}

	return v->data + (idx) * v->_elem_size;
}

extern int
vector__cleanup(struct vector *v)
{
	int ret = 0;

	if (v == NULL) {
		fprintf(stderr, "%s(): received NULL ptr, not doing anything (-1)\n",
				__func__);
		return -1;
	}

	if (v->_max > 0) {
		v->_max = v->n = 0;
		free(v->data);
		v->data = NULL;
	} else {
		ret |= 1;
	}

	/* TODO: improve logic */
	debug_fprintf((stderr, "%s(): freeing v=%p\n", __func__, (void*) v));
	free(v);

	return ret;
}
/* }}} */

/* {{{ queue */
extern struct queue *
queue__new(const int n, const size_t elem_size)
{
	struct queue *q = NULL;

	assert(n >= 1); /* WHO DOES THIS ?!? >:( */
	assert(elem_size > 0);

	q = (struct queue *) s_malloc(sizeof *q);
	q->data = (char *) s_calloc(n, elem_size);
	q->_data_size = elem_size;
	q->head = 0;
	q->n = 0;
	q->_max = n;

	return q;
}

extern int
queue__push(struct queue *q, const void *p)
{
	assert(q != NULL);
	assert(p != NULL);

	if (q->n >= q->_max) {
		#ifdef QUEUE_DEBUG
		fprintf(stderr, "%s(): q->n (%d) >= q->_max (%d), can't push any deeper :-(\n",
				__func__, q->n, q->_max);
		#endif /* QUEUE_DEBUG */
		return -1;
	}

	memcpy(q->data + ((q->head + q->n++) % q->_max) * q->_data_size, p, q->_data_size);
	#ifdef QUEUE_BEBUG
	fprintf(stderr, "%s(): q->head=%d, q->n=%d\n",
			__func__, q->head, q->n);
	#endif

	return 0;
}

extern int
queue__pop(struct queue *q, void *buf)
{
	assert(q != NULL);
	assert(buf != NULL);

	memcpy(buf, q->data + (q->head) * q->_data_size, q->_data_size);
	q->head = (q->head + 1) % q->_max;
	q->n--;
	#ifdef QUEUE_BEBUG
	fprintf(stderr, "%s(): q->head=%d, q->n=%d\n",
			__func__, q->head, q->n);
	#endif

	return 0;
}

extern int
queue__cleanup(struct queue *q)
{
	S_assert(q != NULL);
	if (q == NULL)
		return -1;

	if (q->_max == 0 || q->data == NULL)
		return 1;

	free(q->data);
	q->data = NULL;
	free(q);

	return 0;
}
/* }}} */

/* {{{ aho-corasick */
int
ac__reg_word(struct ac_node *root, const char *w, const int id)
{
	register int i;
	struct st_node *next;

	i = 0;
	while (w[i]) {
		if (root->next[w[i] - 'a'] == NULL) {
			root->next[w[i] - 'a'] = s_calloc(1UL, sizeof *root->next[0]);
		}
		root = root->next[w[i] - 'a'];
		i++;
	}
	root->final_pattern = true;
	root->pattern_id = id;
	root->pattern_len = i - 1;

	return 0;
}

int
ac__count_nodes(struct ac_node *node)
{
	int i, ans = 1;

	for (i = 0; i < 'z' - 'a' + 1; i++) {
		if (node->next[i])
			ans += ac__count_nodes(node->next[i]);
	}

	return ans;
}

int
ac__prefix_func(struct ac_node *acroot)
{
	struct queue *q;
	struct ac_node *nd, *nxt; /* current node in bfs */
	struct ac_node *ppref; /* looks for suitable prefix function value */
	int i;

	q = queue__new(ac__count_nodes(acroot), sizeof acroot);
	queue__push(q, &acroot);
	acroot->prefix = acroot;

	while (q->n) {
		queue__pop(q, &nd);

		for (i = 0; i < 'z' - 'a' + 1; i++) {
			if (nd->next[i] != NULL) {
				nxt = nd->next[i];
				queue__push(q, &nxt);

				/*
				 * So in a situation like
				 *    p  -[c]-> v
				 * we traverse all p's prefix function values until we find
				 * a p* node that has the same -[c]-> edge. Therefore, we have
				 *    p* -[c]-> v*
				 * and v's prefix function will be the v* node.
				 *
				 * nd := p
				 * nxt := v
				 * i := c - 'a'
				 */
				/*
				 * Prefix function value for trie root and
				 * all its direct descendants is trie root.
				 */
				if (nd == acroot) {
					nxt->prefix = nd;
				} else {
					ppref = nd->prefix;
					while (ppref && ppref->next[i] == NULL && ppref != acroot)
						ppref = ppref->prefix;
					nxt->prefix = ppref && ppref->next[i] ? ppref->next[i] : acroot;

					/* The "out" function. */
					if (nxt->prefix->final_pattern)
						nxt->out = nxt->prefix;
					else if (nxt->prefix->out && nxt->prefix->out->final_pattern)
						nxt->out = nxt->prefix->out;
					else {
						S_assert(nxt->out == NULL);
						nxt->out = NULL;
					}
				}
			}
		}
	}

	queue__cleanup(q);
	return 0;
}

int
ac__contains(struct ac_node *ac_dfa, const char *text, struct vector *answer)
{
	register struct ac_node *state = ac_dfa;
	register struct ac_node *out_func = NULL;
	int i = 0;
	int ans = 0;
	struct twotuple push;

	while (text[i]) {
		while (state != ac_dfa && state->next[text[i] - 'a'] == NULL)
			state = state->prefix;

		if (state->next[text[i] - 'a'] != NULL)
			state = state->next[text[i] - 'a'];

		if (state->final_pattern) {
			push.a = i - state->pattern_len;
			push.b = state->pattern_id;
			vector__append(answer, &push);
		}

		if (state->out) {
			out_func = state->out;
			while (out_func) {
				push.a = i - out_func->pattern_len;
				push.b = out_func->pattern_id;
				vector__append(answer, &push);
				out_func = out_func->out;
			}
		}
		i++;
	}

	return ans;
}

void
ac__cleanup(struct ac_node *node)
{
	int i = 0;

	while (i < 'z' - 'a' + 1) {
		if (node->next[i])
			ac__cleanup(node->next[i]);
		i++;
	}
	free(node);
}
/* }}} */

int
main(int argc, char **argv)
{
	char *word, *lf;
	int n;
	struct ac_node *dfa;
	struct vector *answer;
	struct twotuple tt;
	int i;

	dfa = s_calloc(1UL, sizeof *dfa);
	dfa->root = true;
	word = s_malloc(1000002UL);
	answer = vector__new(sizeof (struct twotuple), 6);

	fgets(word, 251, stdin);
	sscanf(word, "%d", &n);
	i = 1;
	while (n--) {
		(void) fgets(word, 251, stdin);
		if (lf = strrchr(word, '\n'), lf)
			*lf = '\0';
		ac__reg_word(dfa, word, i);
		i++;
	}
	ac__prefix_func(dfa);

	fgets(word, 1000001, stdin);
	if (lf = strrchr(word, '\n'), lf != NULL)
		*lf = '\0';
	ac__contains(dfa, word, answer);

	for (i = 0; i < answer->n; i++) {
		tt = * (struct twotuple *) vector__get_by_idx(answer, i);
		printf("%d %d\n", tt.a, tt.b);
	}

	vector__cleanup(answer);
	ac__cleanup(dfa);
	free(word);
	return 0;
}
